SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Computational complexity</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Computational complexity</span></span>

</h1>

</header>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, the <b>computational complexity</b> or simply <b>complexity</b> of an <a href="Algorithm" title="Algorithm">algorithm</a> is the amount of resources required to run it.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Particular focus is given to <a href="Time_complexity" title="Time complexity">computation time</a> (generally measured by the number of needed elementary operations) and <a href="Space_complexity" title="Space complexity">memory storage</a> requirements. The complexity of a <a href="Computational_problem" title="Computational problem">problem</a> is the complexity of the best algorithms that allow solving the problem.

</p><p>The study of the complexity of explicitly given algorithms is called <a href="Analysis_of_algorithms" title="Analysis of algorithms">analysis of algorithms</a>, while the study of the complexity of problems is called <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>. Both areas are highly related, as the complexity of an algorithm is always an <a href="Upper_bound" class="mw-redirect" title="Upper bound">upper bound</a> on the complexity of the problem solved by this algorithm. Moreover, for designing efficient algorithms, it is often fundamental to compare the complexity of a specific algorithm to the complexity of the problem to be solved. Also, in most cases, the only thing that is known about the complexity of a problem is that it is lower than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory.

</p><p>As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function <span class="texhtml"><i>n</i> → <i>f</i>(<i>n</i>)</span>, where <span class="texhtml"><i>n</i></span> is the size of the input and <span class="texhtml"><i>f</i>(<i>n</i>)</span> is either the <a href="Worst-case_complexity" title="Worst-case complexity">worst-case complexity</a> (the maximum of the amount of resources that are needed over all inputs of size <span class="texhtml"><i>n</i></span>) or the <a href="Average-case_complexity" title="Average-case complexity">average-case complexity</a> (the average of the amount of resources over all inputs of size <span class="texhtml"><i>n</i></span>). <a href="Time_complexity" title="Time complexity">Time complexity</a> is generally expressed as the number of required elementary operations on an input of size <span class="texhtml"><i>n</i></span>, where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. <a href="Space_complexity" title="Space complexity">Space complexity</a> is generally expressed as the amount of <a href="Computer_memory" title="Computer memory">memory</a> required by an algorithm on an input of size <span class="texhtml"><i>n</i></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Resources">Resources</h2></div>

<p>The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity.

</p><p>The usual units of time (seconds, minutes etc.) are not used in <a href="Computational_complexity_theory" title="Computational complexity theory">complexity theory</a> because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in <a href="Computer_hardware" title="Computer hardware">computer hardware</a>. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place on <i>any</i> computer. This is achieved by counting the number of <i>elementary operations</i> that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called <i>steps</i>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Bit_complexity">Bit complexity</h3></div>

<p>

Formally, the <i>bit complexity</i> refers to the number of operations on <a href="Bit" title="Bit">bits</a> that are needed for running an algorithm. With most <a href="Models_of_computation" class="mw-redirect" title="Models of computation">models of computation</a>, it equals the time complexity up to a constant factor. On <a href="Computer" title="Computer">computers</a>, the number of operations on <a href="Machine_word" class="mw-redirect" title="Machine word">machine words</a> that are needed is also proportional to the bit complexity. So, the <i>time complexity</i> and the <i>bit complexity</i> are equivalent for realistic models of computation.

</p>

<div class="mw-heading mw-heading3"><h3 id="Space">Space</h3></div>

<p>Another important resource is the size of <a href="Computer_memory" title="Computer memory">computer memory</a> that is needed for running algorithms.

</p>

<div class="mw-heading mw-heading3"><h3 id="Communication">Communication</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Communication_complexity" title="Communication complexity">communication complexity</a></div>

<p>For the class of <a href="Distributed_computation" class="mw-redirect" title="Distributed computation">distributed algorithms</a> that are commonly executed by multiple, interacting parties, the resource that is of most interest is the communication complexity. It is the necessary amount of communication between the executing parties.

</p>

<div class="mw-heading mw-heading3"><h3 id="Others">Others</h3></div>

<p>The number of <a href="Arithmetic_operations" class="mw-redirect" title="Arithmetic operations">arithmetic operations</a> is another resource that is commonly used. In this case, one talks of <b>arithmetic complexity</b>. If one knows an <a href="Upper_bound" class="mw-redirect" title="Upper bound">upper bound</a> on the size of the <a href="Binary_representation" class="mw-redirect" title="Binary representation">binary representation</a> of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor.

</p><p>

For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called <b>bit complexity</b> in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the <a href="Determinant" title="Determinant">determinant</a> of a <span class="texhtml"><i>n</i>×<i>n</i></span> <a href="Integer_matrix" title="Integer matrix">integer matrix</a> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3})}</annotation>

</semantics>

</math></span><img src="./6b04f5c5cfea38f43406d9442387ad28555e2609.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{3})}" loading="lazy"></span> for the usual algorithms (<a href="Gaussian_elimination" title="Gaussian elimination">Gaussian elimination</a>). The bit complexity of the same algorithms is <a href="Exponential_function" title="Exponential function">exponential</a> in <span class="texhtml mvar" style="font-style:italic;">n</span>, because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with <a href="Modular_arithmetic" title="Modular arithmetic">multi-modular arithmetic</a>, the bit complexity may be reduced to <span class="texhtml"><a href="Soft_O_notation" class="mw-redirect" title="Soft O notation"><i>O</i><sup>~</sup>(<i>n</i><sup>4</sup>)</a></span>.

</p><p>In <a href="Sorting" title="Sorting">sorting</a> and <a href="Search_algorithm" title="Search algorithm">searching</a>, the resource that is generally considered is the number of entry comparisons. This is generally a good measure of the time complexity if data are suitably organized.

</p>

<div class="mw-heading mw-heading2"><h2 id="Complexity_as_a_function_of_input_size">Complexity as a function of input size</h2></div>

<p>It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the size <span class="texhtml"><i>n</i></span> (in <a href="Bit" title="Bit">bits</a>) of the input, and therefore, the complexity is a function of <span class="texhtml"><i>n</i></span>. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.

</p><p>The <a href="Worst-case_complexity" title="Worst-case complexity">worst-case complexity</a> is the maximum of the complexity over all inputs of size <span class="texhtml mvar" style="font-style:italic;">n</span>, and the <a href="Average-case_complexity" title="Average-case complexity">average-case complexity</a> is the average of the complexity over all inputs of size <span class="texhtml mvar" style="font-style:italic;">n</span> (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.

</p>

<div class="mw-heading mw-heading2"><h2 id="Asymptotic_complexity">Asymptotic complexity</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Asymptotic_computational_complexity" title="Asymptotic computational complexity">Asymptotic computational complexity</a></div>

<p>It is generally difficult to compute precisely the worst-case and the average-case complexity. In addition, these exact values provide little practical application, as any change of computer or of model of computation would change the complexity somewhat. Moreover, the resource use is not critical for small values of <span class="texhtml mvar" style="font-style:italic;">n</span>, and this makes that, for small <span class="texhtml mvar" style="font-style:italic;">n</span>, the ease of implementation is generally more interesting than a low complexity.

</p><p>For these reasons, one generally focuses on the behavior of the complexity for large <span class="texhtml mvar" style="font-style:italic;">n</span>, that is on its <a href="Asymptotic_analysis" title="Asymptotic analysis">asymptotic behavior</a> when <span class="texhtml mvar" style="font-style:italic;">n</span> tends to the infinity. Therefore, the complexity is generally expressed by using <a href="Big_O_notation" title="Big O notation">big O notation</a>.

</p><p>For example, the usual algorithm for integer <a href="Multiplication" title="Multiplication">multiplication</a> has a complexity of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2}),}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2}),}</annotation>

</semantics>

</math></span><img src="./a19ec17793aaef1d012877a17176f91dfc984de5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.678ex; height:3.176ex;" alt="{\displaystyle O(n^{2}),}" loading="lazy"></span> this means that there is a constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{u}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{u}}</annotation>

</semantics>

</math></span><img src="./3c0ef6c7323dc59b61cf73aa6eabb5c10fcb3db2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.179ex; height:2.009ex;" alt="{\displaystyle c_{u}}" loading="lazy"></span> such that the multiplication of two integers of at most <span class="texhtml mvar" style="font-style:italic;">n</span> digits may be done in a time less than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{u}n^{2}.}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{u}n^{2}.}</annotation>

</semantics>

</math></span><img src="./c6f580a9bb53e96e21a64d69fa3799af43bcd3a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.275ex; height:3.009ex;" alt="{\displaystyle c_{u}n^{2}.}" loading="lazy"></span> This bound is <i>sharp</i> in the sense that the worst-case complexity and the average-case complexity are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n^{2}),}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{2}),}</annotation>

</semantics>

</math></span><img src="./e0a0cfd5246e1f373111ac67cfa132470d5fa417.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.583ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{2}),}" loading="lazy"></span> which means that there is a constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{l}}</annotation>

</semantics>

</math></span><img src="./161bd00c9b87a82436365401180e618862a74b57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.729ex; height:2.009ex;" alt="{\displaystyle c_{l}}" loading="lazy"></span> such that these complexities are larger than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{l}n^{2}.}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{l}n^{2}.}</annotation>

</semantics>

</math></span><img src="./db38d9578155c12942ff99ad13ad19a9186689c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.825ex; height:3.009ex;" alt="{\displaystyle c_{l}n^{2}.}" loading="lazy"></span> The <a href="Radix" title="Radix">radix</a> does not appear in these complexity, as changing of radix changes only the constants <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{u}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{u}}</annotation>

</semantics>

</math></span><img src="./3c0ef6c7323dc59b61cf73aa6eabb5c10fcb3db2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.179ex; height:2.009ex;" alt="{\displaystyle c_{u}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{l}.}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{l}.}</annotation>

</semantics>

</math></span><img src="./6bb65eb2ba4163f0e198bc35fa2eba696e744724.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.376ex; height:2.009ex;" alt="{\displaystyle c_{l}.}" loading="lazy"></span>

</p>

<div class="mw-heading mw-heading2"><h2 id="Models_of_computation">Models of computation</h2></div>

<p>The evaluation of the complexity relies on the choice of a <a href="Model_of_computation" title="Model of computation">model of computation</a>, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, it is generally implicitely assumed as being a <a href="Multitape_Turing_machine" title="Multitape Turing machine">multitape Turing machine</a>, since several more realistic models of computation, such as <a href="Random-access_machine" title="Random-access machine">random-access machines</a> are asymptotically equivalent for most problems. It is only for very specific and difficult problems, such as <a href="Integer_multiplication" class="mw-redirect" title="Integer multiplication">integer multiplication</a> in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n),}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n),}</annotation>

</semantics>

</math></span><img src="./497720dca0f6c8c6268f7a1332b993e597136e8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.765ex; height:2.843ex;" alt="{\displaystyle O(n\log n),}" loading="lazy"></span> that the explicit definition of the model of computation is required for proofs.

</p>

<div class="mw-heading mw-heading3"><h3 id="Deterministic_models">Deterministic models</h3></div>

<p>A <a href="Deterministic_model" class="mw-redirect" title="Deterministic model">deterministic model</a> of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were <a href="%CE%9C-recursive_function" class="mw-redirect" title="Μ-recursive function">recursive functions</a>, <a href="Lambda_calculus" title="Lambda calculus">lambda calculus</a>, and <a href="Turing_machine" title="Turing machine">Turing machines</a>. The model of <a href="Random-access_machine" title="Random-access machine">random-access machines</a> (also called RAM-machines) is also widely used, as a closer counterpart to real <a href="Computer" title="Computer">computers</a>.

</p><p>When the model of computation is not specified, it is generally assumed to be a <a href="Multitape_Turing_machine" title="Multitape Turing machine">multitape Turing machine</a>. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence.

</p>

<div class="mw-heading mw-heading3"><h3 id="Non-deterministic_computation">Non-deterministic computation</h3></div>

<p>In a <a href="Non-deterministic_algorithm" class="mw-redirect" title="Non-deterministic algorithm">non-deterministic model of computation</a>, such as <a href="Non-deterministic_Turing_machine" class="mw-redirect" title="Non-deterministic Turing machine">non-deterministic Turing machines</a>, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to <a href="Quantum_computing" title="Quantum computing">quantum computing</a> via superposed <a href="Entangled_state" class="mw-redirect" title="Entangled state">entangled states</a> in running specific <a href="Quantum_algorithms" class="mw-redirect" title="Quantum algorithms">quantum algorithms</a>, like e.g. <a href="Shor's_algorithm" title="Shor's algorithm">Shor's factorization</a> of yet only small integers (as of March 2018: 21 = 3 × 7).

</p><p>Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the <a href="P_%3D_NP" class="mw-redirect" title="P = NP">P = NP</a> problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class <a href="NP_(complexity)" title="NP (complexity)">NP</a>, if it may be solved in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> on a non-deterministic machine. A problem is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> if, roughly speaking, it is in NP and is not easier than any other NP problem. Many <a href="Combinatorics" title="Combinatorics">combinatorial</a> problems, such as the <a href="Knapsack_problem" title="Knapsack problem">Knapsack problem</a>, the <a href="Travelling_salesman_problem" title="Travelling salesman problem">travelling salesman problem</a>, and the <a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem</a> are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. As of 2017 it is generally conjectured that <span class="nowrap">P ≠ NP,</span> with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.

</p>

<div class="mw-heading mw-heading3"><h3 id="Parallel_and_distributed_computation">Parallel and distributed computation</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main articles: <a href="Parallel_computing" title="Parallel computing">Parallel computing</a> and <a href="Distributed_computing" title="Distributed computing">Distributed computing</a></div>

<p>Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a <a href="Computer_network" title="Computer network">network</a> and is therefore much slower.

</p><p>The time needed for a computation on <span class="texhtml mvar" style="font-style:italic;">N</span> processors is at least the quotient by <span class="texhtml mvar" style="font-style:italic;">N</span> of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.

</p><p>The main complexity problem is thus to design algorithms such that the product of the computation time by the number of processors is as close as possible to the time needed for the same computation on a single processor.

</p>

<div class="mw-heading mw-heading3"><h3 id="Quantum_computing">Quantum computing</h3></div>

<p>A <a href="Quantum_computer" class="mw-redirect" title="Quantum computer">quantum computer</a> is a computer whose model of computation is based on <a href="Quantum_mechanics" title="Quantum mechanics">quantum mechanics</a>. The <a href="Church%E2%80%93Turing_thesis_(complexity_theory)" class="mw-redirect" title="Church–Turing thesis (complexity theory)">Church–Turing thesis</a> applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower <a href="Time_complexity" title="Time complexity">time complexity</a> using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.

</p><p><a href="Quantum_complexity_theory" title="Quantum complexity theory">Quantum complexity theory</a> has been developed to study the <a href="Complexity_class" title="Complexity class">complexity classes</a> of problems solved using quantum computers. It is used in <a href="Post-quantum_cryptography" title="Post-quantum cryptography">post-quantum cryptography</a>, which consists of designing <a href="Cryptographic_protocol" title="Cryptographic protocol">cryptographic protocols</a> that are resistant to attacks by quantum computers.

</p>

<div class="mw-heading mw-heading2"><h2 id="Problem_complexity_(lower_bounds)">Problem complexity (lower bounds)</h2></div>

<p>The complexity of a problem is the <a href="Infimum" class="mw-redirect" title="Infimum">infimum</a> of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.

</p><p>It follows that every complexity of an algorithm, that is expressed with <a href="Big_O_notation" title="Big O notation">big O notation</a>, is also an upper bound on the complexity of the corresponding problem.

</p><p>On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.

</p><p>For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least <a href="Linear_time" class="mw-redirect" title="Linear time">linear</a>, that is, using <a href="Big_omega_notation" class="mw-redirect" title="Big omega notation">big omega notation</a>, a complexity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n).}</annotation>

</semantics>

</math></span><img src="./da500dd2c91bee2a37b31ca985fcda081b7fc5b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.529ex; height:2.843ex;" alt="{\displaystyle \Omega (n).}" loading="lazy"></span>

</p><p>The solution of some problems, typically in <a href="Computer_algebra" title="Computer algebra">computer algebra</a> and <a href="Computational_algebraic_geometry" class="mw-redirect" title="Computational algebraic geometry">computational algebraic geometry</a>, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a <a href="System_of_polynomial_equations" title="System of polynomial equations">system of <span class="texhtml mvar" style="font-style:italic;">n</span> polynomial equations of degree <span class="texhtml mvar" style="font-style:italic;">d</span> in <span class="texhtml mvar" style="font-style:italic;">n</span> indeterminates</a> may have up to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d^{n}}</annotation>

</semantics>

</math></span><img src="./dd9e17da538fa2fc3bf1a54cadada8c21771fd3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.437ex; height:2.343ex;" alt="{\displaystyle d^{n}}" loading="lazy"></span> <a href="Complex_number" title="Complex number">complex</a> solutions, if the number of solutions is finite (this is <a href="B%C3%A9zout's_theorem" title="Bézout's theorem">Bézout's theorem</a>). As these solutions must be written down, the complexity of this problem is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (d^{n}).}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (d^{n}).}</annotation>

</semantics>

</math></span><img src="./1ec900f04067f03ed712312ede0b5a213cbc23e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.571ex; height:2.843ex;" alt="{\displaystyle \Omega (d^{n}).}" loading="lazy"></span> For this problem, an algorithm of complexity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d^{O(n)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d^{O(n)}}</annotation>

</semantics>

</math></span><img src="./807ad57799efff3cd91163256c8be1eb17c095c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.97ex; height:2.843ex;" alt="{\displaystyle d^{O(n)}}" loading="lazy"></span> is known, which may thus be considered as asymptotically quasi-optimal.

</p><p>A nonlinear lower bound of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n\log n)}</annotation>

</semantics>

</math></span><img src="./00663e988b37b064dbfe30791c3ad477907cc3a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.023ex; height:2.843ex;" alt="{\displaystyle \Omega (n\log n)}" loading="lazy"></span> is known for the number of comparisons needed for a <a href="Sorting_algorithm" title="Sorting algorithm">sorting algorithm</a>. Thus the best sorting algorithms are optimal, as their complexity is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n).}</annotation>

</semantics>

</math></span><img src="./d33777001ea38436a3f2b44b2c1fa99268a339c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.765ex; height:2.843ex;" alt="{\displaystyle O(n\log n).}" loading="lazy"></span> This lower bound results from the fact that there are <span class="texhtml"><i>n</i>!</span> ways of ordering <span class="texhtml mvar" style="font-style:italic;">n</span> objects. As each comparison splits in two parts this set of <span class="texhtml"><i>n</i>!</span> orders, the number of <span class="texhtml mvar" style="font-style:italic;">N</span> of comparisons that are needed for distinguishing all orders must verify <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{N}>n!,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{N}>n!,}</annotation>

</semantics>

</math></span><img src="./67b9c361fc15c8a355bf19a7e93d3feb9b794fa2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.641ex; height:3.009ex;" alt="{\displaystyle 2^{N}>n!,}" loading="lazy"></span> which implies <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=\Omega (n\log n),}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=\Omega (n\log n),}</annotation>

</semantics>

</math></span><img src="./674b47471c1c539ad74eeed52d421430f878dd5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.832ex; height:2.843ex;" alt="{\displaystyle N=\Omega (n\log n),}" loading="lazy"></span> by <a href="Stirling's_formula" class="mw-redirect" title="Stirling's formula">Stirling's formula</a>.

</p><p>A standard method for getting lower bounds of complexity consists of <i>reducing</i> a problem to another problem. More precisely, suppose that one may encode a problem <span class="texhtml mvar" style="font-style:italic;">A</span> of size <span class="texhtml mvar" style="font-style:italic;">n</span> into a subproblem of size <span class="texhtml"><i>f</i>(<i>n</i>)</span> of a problem <span class="texhtml mvar" style="font-style:italic;">B</span>, and that the complexity of <span class="texhtml mvar" style="font-style:italic;">A</span> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (g(n)).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (g(n)).}</annotation>

</semantics>

</math></span><img src="./1a36c985f809b094829e7ea1a13090cd717bbf8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.454ex; height:2.843ex;" alt="{\displaystyle \Omega (g(n)).}" loading="lazy"></span> Without loss of generality, one may suppose that the function <span class="texhtml mvar" style="font-style:italic;">f</span> increases with <span class="texhtml mvar" style="font-style:italic;">n</span> and has an <a href="Inverse_function" title="Inverse function">inverse function</a> <span class="texhtml mvar" style="font-style:italic;">h</span>. Then the complexity of the problem <span class="texhtml mvar" style="font-style:italic;">B</span> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (g(h(n))).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (g(h(n))).}</annotation>

</semantics>

</math></span><img src="./0121e250e3514c05af461848788b3b3932ca292b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.602ex; height:2.843ex;" alt="{\displaystyle \Omega (g(h(n))).}" loading="lazy"></span> This is the method that is used to prove that, if <a href="P_%E2%89%A0_NP" class="mw-redirect" title="P ≠ NP">P ≠ NP</a> (an unsolved conjecture), the complexity of every <a href="NP-complete_problem" class="mw-redirect" title="NP-complete problem">NP-complete problem</a> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n^{k}),}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{k}),}</annotation>

</semantics>

</math></span><img src="./98ca27a36c609d5fc18a0d9cdf83f257130042a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.618ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{k}),}" loading="lazy"></span> for every positive integer <span class="texhtml mvar" style="font-style:italic;">k</span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Use_in_algorithm_design">Use in algorithm design</h2></div>

<p>Evaluating the complexity of an algorithm is an important part of <a href="Algorithm_design" class="mw-redirect" title="Algorithm design">algorithm design</a>, as this gives useful information on the performance that may be expected.

</p><p>It is a common misconception that the evaluation of the complexity of algorithms will become less important as a result of <a href="Moore's_law" title="Moore's law">Moore's law</a>, which posits the <a href="Exponential_growth" title="Exponential growth">exponential growth</a> of the power of modern <a href="Computer" title="Computer">computers</a>. This is wrong because this power increase allows working with large input data (<a href="Big_data" title="Big data">big data</a>). For example, when one wants to sort alphabetically a list of a few hundreds of entries, such as the <a href="Bibliography" title="Bibliography">bibliography</a> of a book, any algorithm should work well in less than a second. On the other hand, for a list of a million of entries (the phone numbers of a large town, for example), the elementary algorithms that require <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span> comparisons would have to do a trillion of comparisons, which would need around three hours at the speed of 10 million of comparisons per second. On the other hand, the <a href="Quicksort" title="Quicksort">quicksort</a> and <a href="Merge_sort" title="Merge sort">merge sort</a> require only <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\log _{2}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\log _{2}n}</annotation>

</semantics>

</math></span><img src="./8bb9cc0ed62ae23352f4838dccf462bf04c73b6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.59ex; height:2.676ex;" alt="{\displaystyle n\log _{2}n}" loading="lazy"></span> comparisons (as average-case complexity for the former, as worst-case complexity for the latter). For <span class="texhtml"><i>n</i> = 1,000,000</span>, this gives approximately 30,000,000 comparisons, which would only take 3 seconds at 10 million comparisons per second.

</p><p>Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.

</p>

<ul><li><a href="Computational_complexity_of_mathematical_operations" title="Computational complexity of mathematical operations">Computational complexity of mathematical operations</a></li>

<li><a href="Chinese_Postman_Problem_Complexity_List" class="mw-redirect" title="Chinese Postman Problem Complexity List">Chinese Postman Problem Complexity List</a></li>

<li><a href="Master_theorem_(analysis_of_algorithms)" title="Master theorem (analysis of algorithms)">Master theorem (analysis of algorithms)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFVadhan2011" class="citation cs2"><a href="Salil_Vadhan" title="Salil Vadhan">Vadhan, Salil</a> (2011), <a rel="nofollow" class="external text" href="https://people.seas.harvard.edu/~salil/research/ComputationalComplexity-2ndEd.pdf">"Computational Complexity"</a> <span class="cs1-format">(PDF)</span>, in van Tilborg, Henk C. A.; Jajodia, Sushil (eds.), <i>Encyclopedia of Cryptography and Security</i>, Springer, pp. <span class="nowrap">235–</span>240, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4419-5906-5_442">10.1007/978-1-4419-5906-5_442</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781441959065</bdi></cite></span>

</li>

</ol></div></div>

<ul><li><cite id="CITEREFAroraBarak2009" class="citation cs2"><a href="Sanjeev_Arora" title="Sanjeev Arora">Arora, Sanjeev</a>; Barak, Boaz (2009), <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/theory/complexity/"><i>Computational Complexity: A Modern Approach</i></a>, <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-42426-4</bdi>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1193.68112">1193.68112</a></cite></li>

<li><cite id="CITEREFCalude1988" class="citation cs2"><a href="Cristian_Calude" title="Cristian Calude">Calude, Cristian</a> (1988), <i>Theories of Computational Complexity</i>, <a href="Elsevier" title="Elsevier">Elsevier</a>, p. 487, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780444703569</bdi></cite></li>

<li><cite id="CITEREFDuKo,_Ker-I2000" class="citation cs2">Du, Ding-Zhu; Ko, Ker-I (2000), <i>Theory of Computational Complexity</i>, <a href="John_Wiley_%26_Sons" class="mw-redirect" title="John Wiley & Sons">John Wiley & Sons</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-34506-0</bdi>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0167-5060">0167-5060</a></cite></li>

<li><cite id="CITEREFGareyJohnson1979" class="citation book cs2"><a href="Michael_Garey" title="Michael Garey">Garey, Michael R.</a>; <a href="David_S._Johnson" title="David S. Johnson">Johnson, David S.</a> (1979), <i><a href="Computers_and_Intractability" title="Computers and Intractability">Computers and Intractability: A Guide to the Theory of NP-Completeness</a></i>, Series of Books in the Mathematical Sciences (1st ed.), New York: <a href="W._H._Freeman_and_Company" title="W. H. Freeman and Company">W. H. Freeman and Company</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780716710455</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0519066">0519066</a>, <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/247570676">247570676</a></cite></li>

<li><cite id="CITEREFGoldreich2008" class="citation cs2"><a href="Oded_Goldreich" title="Oded Goldreich">Goldreich, Oded</a> (2008), <a rel="nofollow" class="external text" href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html"><i>Computational Complexity: A Conceptual Perspective</i></a>, Cambridge University Press</cite></li>

<li><cite id="CITEREFvan_Leeuwen1990" class="citation cs2"><a href="Jan_van_Leeuwen" title="Jan van Leeuwen">van Leeuwen, Jan</a>, ed. (1990), <i>Handbook of theoretical computer science (vol. A): algorithms and complexity</i>, <a href="MIT_Press" title="MIT Press">MIT Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-444-88071-0</bdi></cite></li>

<li><cite id="CITEREFPapadimitriou1994" class="citation cs2"><a href="Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou, Christos</a> (1994), <i>Computational Complexity</i> (1st ed.), Addison Wesley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-53082-1</bdi></cite></li>

<li><cite id="CITEREFSipser2006" class="citation cs2"><a href="Michael_Sipser" title="Michael Sipser">Sipser, Michael</a> (2006), <i><a href="Introduction_to_the_Theory_of_Computation" title="Introduction to the Theory of Computation">Introduction to the Theory of Computation</a></i> (2nd ed.), USA: <a href="Thomson_Learning" class="mw-redirect" title="Thomson Learning">Thomson Course Technology</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-534-95097-3</bdi></cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Computer_science1050" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Computer_science1050" style="font-size:114%;margin:0 4em"><a href="Computer_science" title="Computer science">Computer science</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div>Note: This template roughly follows the 2012 <a href="ACM_Computing_Classification_System" title="ACM Computing Classification System">ACM Computing Classification System</a>.</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Printed_circuit_board" title="Printed circuit board">Printed circuit board</a></li>

<li><a href="Peripheral" title="Peripheral">Peripheral</a></li>

<li><a href="Integrated_circuit" title="Integrated circuit">Integrated circuit</a></li>

<li><a href="Very-large-scale_integration" title="Very-large-scale integration">Very-large-scale integration</a></li>

<li><a href="System_on_a_chip" title="System on a chip">System on a chip</a> (SoC)</li>

<li><a href="Green_computing" title="Green computing">Energy consumption</a> (green computing)</li>

<li><a href="Electronic_design_automation" title="Electronic design automation">Electronic design automation</a></li>

<li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li>

<li><a href="Processor_(computing)" title="Processor (computing)">Processor</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Computer systems organization</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Computer_architecture" title="Computer architecture">Computer architecture</a></li>

<li><a href="Dependability" title="Dependability">Dependability</a></li>

<li><a href="Embedded_system" title="Embedded system">Embedded system</a></li>

<li><a href="Real-time_computing" title="Real-time computing">Real-time computing</a></li>

<li><a href="Cyber-physical_system" title="Cyber-physical system">Cyber-physical system</a></li>

<li><a href="Fault_tolerance" title="Fault tolerance">Fault tolerance</a></li>

<li><a href="Wireless_sensor_network" title="Wireless sensor network">Wireless sensor network</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_network" title="Computer network">Networks</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Network_architecture" title="Network architecture">Network architecture</a></li>

<li><a href="Communication_protocol" title="Communication protocol">Network protocol</a></li>

<li><a href="Networking_hardware" title="Networking hardware">Network components</a></li>

<li><a href="Network_scheduler" title="Network scheduler">Network scheduler</a></li>

<li><a href="Network_performance" title="Network performance">Network performance evaluation</a></li>

<li><a href="Network_service" title="Network service">Network service</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software organization</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpreter_(computing)" title="Interpreter (computing)">Interpreter</a></li>

<li><a href="Middleware" title="Middleware">Middleware</a></li>

<li><a href="Virtual_machine" title="Virtual machine">Virtual machine</a></li>

<li><a href="Operating_system" title="Operating system">Operating system</a></li>

<li><a href="Software_quality" title="Software quality">Software quality</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Programming_language_theory" title="Programming language theory">Software notations</a> and <a href="Programming_tool" title="Programming tool">tools</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Programming_paradigm" title="Programming paradigm">Programming paradigm</a></li>

<li><a href="Programming_language" title="Programming language">Programming language</a></li>

<li><a href="Compiler_construction" class="mw-redirect" title="Compiler construction">Compiler</a></li>

<li><a href="Domain-specific_language" title="Domain-specific language">Domain-specific language</a></li>

<li><a href="Modeling_language" title="Modeling language">Modeling language</a></li>

<li><a href="Software_framework" title="Software framework">Software framework</a></li>

<li><a href="Integrated_development_environment" title="Integrated development environment">Integrated development environment</a></li>

<li><a href="Software_configuration_management" title="Software configuration management">Software configuration management</a></li>

<li><a href="Library_(computing)" title="Library (computing)">Software library</a></li>

<li><a href="Software_repository" title="Software repository">Software repository</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Software_development" title="Software development">Software development</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Control_flow" title="Control flow">Control variable</a></li>

<li><a href="Software_development_process" title="Software development process">Software development process</a></li>

<li><a href="Requirements_analysis" title="Requirements analysis">Requirements analysis</a></li>

<li><a href="Software_design" title="Software design">Software design</a></li>

<li><a href="Software_construction" title="Software construction">Software construction</a></li>

<li><a href="Software_deployment" title="Software deployment">Software deployment</a></li>

<li><a href="Software_engineering" title="Software engineering">Software engineering</a></li>

<li><a href="Software_maintenance" title="Software maintenance">Software maintenance</a></li>

<li><a href="Programming_team" title="Programming team">Programming team</a></li>

<li><a href="Open-source_software" title="Open-source software">Open-source model</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Theory_of_computation" title="Theory of computation">Theory of computation</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Model_of_computation" title="Model of computation">Model of computation</a>

<ul><li><a href="Stochastic_computing" title="Stochastic computing">Stochastic</a></li></ul></li>

<li><a href="Formal_language" title="Formal language">Formal language</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata theory</a></li>

<li><a href="Computability_theory" title="Computability theory">Computability theory</a></li>

<li><a href="Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a></li>

<li><a href="Logic_in_computer_science" title="Logic in computer science">Logic</a></li>

<li><a href="Semantics_(computer_science)" title="Semantics (computer science)">Semantics</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Algorithm" title="Algorithm">Algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algorithm_design" class="mw-redirect" title="Algorithm design">Algorithm design</a></li>

<li><a href="Analysis_of_algorithms" title="Analysis of algorithms">Analysis of algorithms</a></li>

<li><a href="Algorithmic_efficiency" title="Algorithmic efficiency">Algorithmic efficiency</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized algorithm</a></li>

<li><a href="Computational_geometry" title="Computational geometry">Computational geometry</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mathematics of <a href="Computing" title="Computing">computing</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Discrete_mathematics" title="Discrete mathematics">Discrete mathematics</a></li>

<li><a href="Probability" title="Probability">Probability</a></li>

<li><a href="Statistics" title="Statistics">Statistics</a></li>

<li><a href="Mathematical_software" title="Mathematical software">Mathematical software</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Mathematical_analysis" title="Mathematical analysis">Mathematical analysis</a></li>

<li><a href="Numerical_analysis" title="Numerical analysis">Numerical analysis</a></li>

<li><a href="Theoretical_computer_science" title="Theoretical computer science">Theoretical computer science</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Information_system" title="Information system">Information systems</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Database" title="Database">Database management system</a></li>

<li><a href="Computer_data_storage" title="Computer data storage">Information storage systems</a></li>

<li><a href="Enterprise_information_system" title="Enterprise information system">Enterprise information system</a></li>

<li><a href="Social_software" title="Social software">Social information systems</a></li>

<li><a href="Geographic_information_system" title="Geographic information system">Geographic information system</a></li>

<li><a href="Decision_support_system" title="Decision support system">Decision support system</a></li>

<li><a href="Industrial_process_control" title="Industrial process control">Process control system</a></li>

<li><a href="Multimedia_database" title="Multimedia database">Multimedia information system</a></li>

<li><a href="Data_mining" title="Data mining">Data mining</a></li>

<li><a href="Digital_library" title="Digital library">Digital library</a></li>

<li><a href="Computing_platform" title="Computing platform">Computing platform</a></li>

<li><a href="Digital_marketing" title="Digital marketing">Digital marketing</a></li>

<li><a href="World_Wide_Web" title="World Wide Web">World Wide Web</a></li>

<li><a href="Information_retrieval" title="Information retrieval">Information retrieval</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_security" title="Computer security">Security</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cryptography" title="Cryptography">Cryptography</a></li>

<li><a href="Formal_methods" title="Formal methods">Formal methods</a></li>

<li><a href="Security_hacker" title="Security hacker">Security hacker</a></li>

<li><a href="Security_service_(telecommunication)" title="Security service (telecommunication)">Security services</a></li>

<li><a href="Intrusion_detection_system" title="Intrusion detection system">Intrusion detection system</a></li>

<li><a href="Hardware_security" title="Hardware security">Hardware security</a></li>

<li><a href="Network_security" title="Network security">Network security</a></li>

<li><a href="Information_security" title="Information security">Information security</a></li>

<li><a href="Application_security" title="Application security">Application security</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a class="external text external" href="https://en.wikipedia.org/wiki/Human-centered_computing">Human–centered computing</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interaction_design" title="Interaction design">Interaction design</a></li>

<li><a href="Augmented_reality" title="Augmented reality">Augmented reality</a></li>

<li><a href="Virtual_reality" title="Virtual reality">Virtual reality</a></li>

<li><a href="Social_computing" title="Social computing">Social computing</a></li>

<li><a href="Ubiquitous_computing" title="Ubiquitous computing">Ubiquitous computing</a></li>

<li><a href="Visualization_(graphics)" title="Visualization (graphics)">Visualization</a></li>

<li><a href="Computer_accessibility" title="Computer accessibility">Accessibility</a></li>

<li><a href="Human%E2%80%93computer_interaction" title="Human–computer interaction">Human–computer interaction</a></li>

<li><a href="Mobile_computing" title="Mobile computing">Mobile computing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Concurrent_computing" title="Concurrent computing">Concurrent computing</a></li>

<li><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></li>

<li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Artificial_intelligence" title="Artificial intelligence">Artificial intelligence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Natural_language_processing" title="Natural language processing">Natural language processing</a></li>

<li><a href="Knowledge_representation_and_reasoning" title="Knowledge representation and reasoning">Knowledge representation and reasoning</a></li>

<li><a href="Computer_vision" title="Computer vision">Computer vision</a></li>

<li><a href="Automated_planning_and_scheduling" title="Automated planning and scheduling">Automated planning and scheduling</a></li>

<li><a href="Mathematical_optimization" title="Mathematical optimization">Search methodology</a></li>

<li><a href="Control_theory" title="Control theory">Control method</a></li>

<li><a href="Philosophy_of_artificial_intelligence" title="Philosophy of artificial intelligence">Philosophy of artificial intelligence</a></li>

<li><a href="Distributed_artificial_intelligence" title="Distributed artificial intelligence">Distributed artificial intelligence</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Machine_learning" title="Machine learning">Machine learning</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Supervised_learning" title="Supervised learning">Supervised learning</a></li>

<li><a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li>

<li><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></li>

<li><a href="Multi-task_learning" title="Multi-task learning">Multi-task learning</a></li>

<li><a href="Cross-validation_(statistics)" title="Cross-validation (statistics)">Cross-validation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_graphics" title="Computer graphics">Graphics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Computer_animation" title="Computer animation">Animation</a></li>

<li><a href="Rendering_(computer_graphics)" title="Rendering (computer graphics)">Rendering</a></li>

<li><a href="Photograph_manipulation" title="Photograph manipulation">Photograph manipulation</a></li>

<li><a href="Graphics_processing_unit" title="Graphics processing unit">Graphics processing unit</a></li>

<li><a href="Image_compression" title="Image compression">Image compression</a></li>

<li><a href="Solid_modeling" title="Solid modeling">Solid modeling</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Applied computing</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Quantum_computing" title="Quantum computing">Quantum computing</a></li>

<li><a href="E-commerce" title="E-commerce">E-commerce</a></li>

<li><a href="Enterprise_software" title="Enterprise software">Enterprise software</a></li>

<li><a href="Computational_mathematics" title="Computational mathematics">Computational mathematics</a></li>

<li><a href="Computational_physics" title="Computational physics">Computational physics</a></li>

<li><a href="Computational_chemistry" title="Computational chemistry">Computational chemistry</a></li>

<li><a href="Computational_biology" title="Computational biology">Computational biology</a></li>

<li><a href="Computational_social_science" title="Computational social science">Computational social science</a></li>

<li><a href="Computational_engineering" title="Computational engineering">Computational engineering</a></li>

<li>Differentiable computing</li>

<li><a href="Health_informatics" title="Health informatics">Computational healthcare</a></li>

<li><a href="Digital_art" title="Digital art">Digital art</a></li>

<li><a href="Electronic_publishing" title="Electronic publishing">Electronic publishing</a></li>

<li><a href="Cyberwarfare" title="Cyberwarfare">Cyberwarfare</a></li>

<li><a href="Electronic_voting" title="Electronic voting">Electronic voting</a></li>

<li><a href="Video_game" title="Video game">Video games</a></li>

<li><a href="Word_processor" title="Word processor">Word processing</a></li>

<li><a href="Operations_research" title="Operations research">Operations research</a></li>

<li><a href="Educational_technology" title="Educational technology">Educational technology</a></li>

<li><a href="Document_management_system" title="Document management system">Document management</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category</li>

<li><span class="noviewer" typeof="mw:File"><span title="Outline"></span></span> <a href="Outline_of_computer_science" title="Outline of computer science">Outline</a></li>

<li><span class="noviewer" typeof="mw:File"><span></span></span> Glossaries</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-31" href="https://en.wikipedia.org/wiki/?title=Computational_complexity&oldid=1283260642">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>